#include "stack.h"

#define WIDTH 10
#define HEIGHT 10

#define STARTX 1
#define STARTY 1
#define DISTX 8
#define DISTY 8
#define STACK_MAX 2000

#define WAY 0
#define NOWAY 1
#define FOUND 2

int matrix[WIDTH][HEIGHT] = {1,1,1,1,1,1,1,1,1,1
							,1,0,0,0,0,0,0,0,0,1
							,1,1,0,1,1,1,0,1,0,1
							,1,1,0,1,0,1,0,0,1,1
							,1,0,0,0,0,1,1,0,1,1
							,1,0,1,1,0,0,1,0,1,1
							,1,0,1,1,1,0,1,0,0,1
							,1,0,0,0,1,0,0,1,0,1
							,1,1,1,0,1,0,1,1,0,1
							,1,1,1,1,1,1,1,1,1,1};


int		step_to_num(int x, int y);
bool	num_to_step(int num, int* x, int *y);
bool	stack_find_road(int x,int y);
bool	re_find_road(int x,int y);


int main()
{
	int x,y;
	int i,cstep,cstack;
	my_stack step;
	stack_create(&step,STACK_MAX);
	stack_push(&step,step_to_num(STARTX,STARTY));
	matrix[STARTX][STARTY] = FOUND;
	while(true)
	{
		stack_get_top(&step,&cstep);
		stack_get_count(&step,&cstack);
		num_to_step(cstep,&x,&y);
		if(x == DISTX && y == DISTY)
		  break;
		if(x+1 < WIDTH - 1)
		{	
			if(matrix[x+1][y] == WAY)
			{
				matrix[x+1][y] = FOUND;
				stack_push(&step,step_to_num(x+1,y));
				continue;
			}
		}
		if(x-1 > 0)
		{
			if(matrix[x-1][y] == WAY)
			{
				matrix[x-1][y] = FOUND;
				stack_push(&step,step_to_num(x-1,y));
				continue;
			}
		}
		if(y+1 < WIDTH - 1)
		{
			if(matrix[x][y+1] == WAY)
			{
				matrix[x][y+1] = FOUND;
				stack_push(&step,step_to_num(x,y+1));
				continue;
			}
		}
		if(y-1 > 0)
		{
			if(matrix[x][y-1] == WAY)
			{
				matrix[x][y-1] = FOUND;
				stack_push(&step,step_to_num(x,y-1));
				continue;
			}
		}
		stack_pop(&step,&cstack);
	}
	stack_get_count(&step,&cstack);
	printf("%d\n",cstack);

	while(cstack)
	{
		stack_pop(&step,&cstep);
		num_to_step(cstep,&x,&y);
		printf("(%d,%d)\n",x,y);
		stack_get_count(&step,&cstack);
	}


	/*if(!re_find_road(7,1))
	  {
	  printf("There is no way!\n");
	  return 0;
	  }
	  else
		}
	  {
	  printf("OK!Way is found!\n");

	  }*/


	return 0;
}

bool re_find_road(int x,int y)
{
	if(x == DISTX && y == DISTY)
	{
		printf("(%d,%d)\n",x,y);
		return true;
	}
	if(matrix[x][y] != WAY)
	  return false;
	matrix[x][y] = FOUND;
	if(x-1 > 0)
	{
		if(re_find_road(x-1,y))
		{
			printf("(%d,%d)\n",x,y);
			return	 true;
		}
	}
	if(x+1 < 9)
	{
		if(re_find_road(x+1,y))
		{
			printf("(%d,%d)\n",x,y);
			return true;
		}
	}
	if(y-1 > 0)
	{
		if(re_find_road(x,y-1))
		{
			printf("(%d,%d)\n",x,y);
			return true;
		}
	}
	if(y+1 < 9)
	{
		if(re_find_road(x,y+1))
		{
			printf("(%d,%d)\n",x,y);
			return true;
		}
	}
	return false;
}

int step_to_num(int x,int y)
{
	return x*100 + y;
}

bool num_to_step(int step, int* x,int* y)
{
	*x = (int)(step / 100);
	*y = step - 100 * (*x);
	return true;
}

